11. Container With Most Water

Medium

題目描述

Description

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

解答

Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let mostWater = 0;

  while (right > left) {
    const waterCurrently =
      Math.min(height[left], height[right]) * (right - left);

    mostWater = Math.max(mostWater, waterCurrently);

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return mostWater;
};

解題思路

1. 先定義好 left pointer 和 right pointer 分別指向 height 的頭與尾，以及 mostWater 紀錄目前的最大水量值。

  let left = 0;
  let right = height.length - 1;
  let mostWater = 0;

2. 重複執行程式直到 right 和 left 重合。

while (right > left) {}

3. 使用 waterCurrently 算出目前水量，因為最大水兩高度是由兩邊中較短的決定的（假設一邊是 8 一邊是 5，水最高只能到 5，再多就會從水槽流出，而 right - left 是寬度，長 * 寬就是目前水量了。 若 waterCurrently > mostWater 則更新。

const waterCurrently = Math.min(height[left], height[right]) * (right - left);

mostWater = Math.max(mostWater, waterCurrently);

4. 如果左邊較短的話就把 left pointer 向右移動，反之則把 right point 向左移。

if (height[left] < height[right]) {
  left++;
} else {
  right--;
}

5. 最後回傳 mostWater 就是答案了。

return mostWater;

心得

練習 Two Pointers，題目光看描述覺得很抽象，但有圖片輔助說明有好懂了不少！